package com.czk.algorithm.greedy.practice;

import java.util.*;

/**
 * @Author:ChenZhangKun
 * @Date: 2020/8/26 23:41
 */
@SuppressWarnings("all")
public class Greedy {
    public static void main(String[] args) {
        // 创建HashMap存储电台
        Map<String, HashSet<String>> map=new HashMap<>();
        // 初始化电台
        HashSet<String> hashSet1=new HashSet<>();
        hashSet1.add("北京");
        hashSet1.add("上海");
        hashSet1.add("天津");
        HashSet<String> hashSet2=new HashSet<>();
        hashSet2.add("广州");
        hashSet2.add("北京");
        hashSet2.add("深圳");
        HashSet<String> hashSet3=new HashSet<>();
        hashSet3.add("成都");
        hashSet3.add("上海");
        hashSet3.add("杭州");
        HashSet<String> hashSet4=new HashSet<>();
        hashSet4.add("天津");
        hashSet4.add("上海");
        HashSet<String> hashSet5=new HashSet<>();
        hashSet5.add("杭州");
        hashSet5.add("大连");
        // 加入map
        map.put("k1",hashSet1);
        map.put("k2",hashSet2);
        map.put("k3",hashSet3);
        map.put("k4",hashSet4);
        map.put("k5",hashSet5);
        // 结果集
        List<String> result=new ArrayList<>();
        // 创建all areas,存放所有的地区
        HashSet<String> allAreas=new HashSet<>();
        for (String s : map.keySet()) {
            for (String s1 : map.get(s)) {
                allAreas.add(s1);
            }
        }
        // 创建临时集合
        HashSet<String> tempList=new HashSet<>();
        // 定义临时变量存储key
        String maxkey;
        while (allAreas.size()!=0){
            maxkey=null;
            // 遍历集合
            for (String s : map.keySet()) {
                // 先将templist清空
                tempList.clear();
                // 拿到key的值
                HashSet<String> hashSet = map.get(s);
                // 将其加入tempSet
                tempList.addAll(hashSet);
                // 求与总集合的交集
                tempList.retainAll(allAreas);
                if (tempList.size()>0&&(maxkey==null||tempList.size()>map.get(maxkey).size())){
                    maxkey=s;
                }
            }
            // 遍历完成
            if (maxkey!=null){
                // 拿到值
                HashSet<String> hashSet = map.get(maxkey);
                allAreas.removeAll(hashSet);
                result.add(maxkey);
            }
        }
        System.out.println(result);
    }
}
class Test{
    public static void main(String[] args) {
        List<String> list=new ArrayList<>();
        System.out.println(list);
    }
}
